package quicksort;

import java.util.List;

import _general.ObjectInterface;
import _general.problem.SortAlgorithm;

public class Quicksort extends SortAlgorithm {
	public Quicksort(List<ObjectInterface> unsortList) {
		super(unsortList);
		setName("Quicksort");
	}
	
	public Quicksort() {	
		setName("Quicksort");
	}
	
	@Override
	public void start() {
		sortAlg(getElementList(), 0, getElementList().size()-1);
	}
	
	private void sortAlg(List<ObjectInterface> A, int left, int right) {
		if (left < right) {
			int[] pq = partition (A, left, right);
			sortAlg(A, left, pq[0]);
			sortAlg(A, pq[1], right);
		}
	}
	
	private int[] partition(List<ObjectInterface> A, int left, int right) {
		int i = left, j = right;
		ObjectInterface p = get(right);
		
		while (i <= j) {
			while (get(i).getId() < p.getId()) {
				i++;
			}
			while (get(j).getId() > p.getId()) {
				j--;
			}
			
			if (i <= j) {
				ObjectInterface swap = get(i);
				set(i, get(j));
				set(j, swap);
				
				i++; j--;
			}
		}
		
		return new int[]{j,i};
	}
}
